/**
 * 543. 二叉树的直径
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 */
const { createTreeNode } = require('../../libs/public');

let max = 0;

/**
 * @param {TreeNode} root
 * @return {number}
 */
function dfs(root) {
  if (!root) {
    return 0;
  }
  const left = dfs(root.left);
  const right = dfs(root.right);
  const sum = left + right;
  if (sum > max) {
    max = sum;
  }
  return Math.max(left, right) + 1;
}

/**
 * @param {TreeNode} root
 * @return {number}
 */
function diameterOfBinaryTree(root) {
  max = 0;
  dfs(root);
  return max;
}

console.log(diameterOfBinaryTree(createTreeNode([1, 2, 3, 4, 5])) === 3);
